package com.simon.study.algorithm.collect;

import java.util.ArrayDeque;
import java.util.Deque;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/22 3:29 上午
 */
public class ListCommon {
    /**
     * summary of sort
     *
     * fundamention of hashmap, hashset
     *
     * beginning of node
     */
    public static boolean isPalindrome(LNode head){
        LNode dup = head;
        Deque<LNode> nodeStack = new ArrayDeque<>();

        while (dup != null){
            nodeStack.addFirst(dup);
            dup = dup.next;
        }

        dup = head;
        while(dup != null){
            if(!dup.data.equals(nodeStack.pollFirst())){ return false; }
            dup = dup.next;
        }
        return true;
    }

    public static boolean isPalindrome2(LNode head){
        if(head == null || head.next == null){
            return true;
        }

        LNode slow = head, fast = head;

        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = slow.next;

        Deque<LNode> nodes = new ArrayDeque<>();
        while (slow != null){
            nodes.push(slow);
            slow = slow.next;
        }

        LNode dup = head;
        while (!nodes.isEmpty()){
            if(dup.data != nodes.pollFirst().data){ return false; }
            dup = dup.next;
        }
        return true;
    }

    public static boolean isPalindrome3(LNode node){
        LNode slow = node, fast = node;

        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        LNode right = slow.next; slow.next = null;
        boolean res = true;

        fast = reverse(right);
        LNode dup = node;

        while (dup != null && fast != null){
            if(dup.data != fast.data){res = false; break;}
            dup  =  dup.next;
            fast = fast.next;
        }

        slow.next = reverse(right);

        return res;
    }



    public static LNode reverse(LNode node){
        LNode pre = null, next;
        while (node !=null){
            next = node.next;
            node.next = pre;
            pre  = node;
            node = next;
        }
        return pre;
    }

    @NoArgsConstructor
    public static class LNode {
        Integer data;

        @Setter
        LNode next;

        /** when for random */
        LNode random;

        public LNode(Integer value, LNode next) {
            this.data = value;
            this.next = next;
        }

        public LNode(Integer data, LNode next, LNode random) {
            this.data = data;
            this.next = next;
            this.random = random;
        }
    }



    /**
     * list
     *
     * circle
     */
    public static LNode getLoopNode(LNode node){
        if(node == null || node.next == null || node.next.next == null){ return null; }

        LNode slow = node.next, fast = node.next.next;

        while (slow != fast){
            if(fast.next == null || fast.next.next == null){ return null; }
            slow = slow.next;
            fast = fast.next.next;
        }

        fast = node;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }


    /**
     * both list without loop
     * might meet in a same node
     */
    public static LNode getNoLoop(LNode head1, LNode head2){
        LNode node1 = head1, node2 = head2; int n = 0;
        while (node1.next != null){
            n++;
            node1 = node1.next;
        }

        while (node2.next != null){
            n--;
            node2 = node2.next;
        }

        if(node1 != node2){ return null; }

        node1 = n > 0 ? head1 : head2;
        node2 = node1 == head1 ? head2 : head1;
        n = Math.abs(n);

        while (n != 0){ n--; node1 = node1.next; }

        while (node1 != node2 ){
            node1 = node1.next;
            node2 = node2.next;
        }

        return node1;
    }


    public static LNode getCommonNodeWithLoop(LNode head1, LNode head2){
        /**
         *   a      o        a
         *   |      |        |
         *   b      p        b
         *   |      |
         *   d -    s -
         *   |   e  |   r
         *   f -    t -
         */
        LNode loopnode1 = getLoopNode(head1);
        LNode loopnode2 = getLoopNode(head2);

        if(loopnode1 == null && loopnode2 == null){
            return getNoLoop(head1, head2);
        }

        if(loopnode1 != null && loopnode2 != null){
            return bothLoop(head1, loopnode1, head2, loopnode2);
        }
        return null;
    }

    public static LNode bothLoop(LNode head1, LNode loop1, LNode head2, LNode loop2){
        LNode cur1 = null, cur2 = null;

        if(loop1 == loop2){
            cur1 = head1; cur2 = head2; int n = 0;

            while (cur1 != loop1){
                n++;
                cur1 = cur1.next;
            }

            while (cur2 != loop2){
                n--;
                cur2 = cur2.next;
            }

            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;

            n = Math.abs(n);
            while ( n > 0){
                n--;
                cur1 = cur1.next;
            }

            while (cur1 != cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else{
            cur1 = loop1.next; cur2 = loop2.next;
            while (cur2 != loop2 && cur2 != cur1){
                cur2 = cur2.next;
            }
            if(cur2 == loop2){ return null; }
            else return loop1;
        }
    }
}
